<?php
// +----------------------------------------------------------------------
// | 数据结构（Data Structure）
// | 1.线性结构
// | 2.数组、矩阵、广义表
// | 3.数
// | 4.图
// | 5.查找
// | 6.排序
// +----------------------------------------------------------------------
namespace helper\structure;

class Search
{
    /**
     * 朴素的模式匹配算法（Brute-Force(布鲁特-福斯算法)） [串的模式匹配] 类似strpos()
     * @param string $s
     * @param string $t
     * @param int $pos
     * @return int
     */
    public function bFSearch(string $s, string $t, int $pos = 0): int
    {
        // i,j分别用于指出主串字符和模式串字符的位置
        $i = $pos;
        $j = 0;
        // 计算主串和模式串的长度
        $sLen = strlen($s);
        $tLen = strlen($t);
        while ($i < $sLen && $j < $tLen) {
            if ($s[$i] == $t[$j]) {
                $i++;
                $j++;
            } else {
                // 主串字符的位置指针回退
                $i = $i - $j + 1;
                $j = 0;
            }

        }
        if ($j >= $tLen) {
            return $i - $tLen;
        }
        return -1;
    }

    /**
     * 求模式串
     * @param string $str
     * @return array
     */
    private function next(string $str): array
    {
        $next[0] = -1;//next[0]初始化为-1
        $i       = 0;
        $j       = -1;
        $sLen    = strlen($str);
        while ($i < $sLen) {
            if ($j === -1 || $str[$i] === $str[$j]) {
                $i++;
                $j++;
                $next[$i] = $j;
            } else {
                $j = $next[$j];
            }
        }
        return $next;
    }

    /**
     * 改进的模式匹配算法 (KMP算法) [串的模式匹配] 类似strpos()
     * KMP精要：KMP在进行朴素匹配时，如果发现不匹配字符时，通过对已经匹配的那部分字符串的最大前缀来快速找到下一个模式串需要匹配的位置。
     * KMP对模式进行预处理时间复杂度O(m)，匹配时间复杂度O(n)，总的KMP时间复杂度为O(m+n)。
     * @param string $s
     * @param string $p
     * @param int $pos
     * @return int
     */
    function KMPSearch(string $s, string $p, int $pos = 0): int
    {
        // 利用模式串p的next函数求p在字符串s中从第$pos个字符串开始的位置
        $next = $this->next($p);
        $i    = $pos - 1;
        $j    = -1;
        $sLen = strlen($s);
        $pLen = strlen($p);
        while ($i < $sLen && $j < $pLen) {
            if ($j === -1 || $s[$i] === $p[$j]) {
                $i++;
                $j++;
            } else {
                $j = $next[$j];
            }
        }
        if ($j === $pLen) {
            return $i - $j;
        }
        return -1;
    }

    /**
     * 深度优先搜索 [图的搜索算法]
     * @return void
     */
    function DPSSearch()
    {

    }

    /**
     * 广度优先搜索/宽度优先搜索算法 [图的搜索算法]
     * 思路分析： BFS并不使用经验法则算法。从算法的观点，所有因为展开节点而得到的子节点都会被加进一个先进先出的队列中
     * 时间复杂度：O(n)
     * Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。
     * 其别名又叫BFS，属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。
     * 换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。
     * @return void
     */
    function BFSSearch()
    {

    }

    /**
     * [静态查找表] 顺序查找
     * 顺序查找也称为线形查找，从数据结构线形表的一端开始，顺序扫描，依次将扫描到的结点关键字与给定值k相比较，若相等则表示查找成功；
     * 若扫描结束仍没有找到关键字等于k的结点，表示查找失败。
     * @param array $arr
     * @param int $num
     * @return int
     */
    function sequelSearch(array $arr, int $num): int
    {
        $len = count($arr);
        for ($i = 0; $i < $len; $i++) {
            if ($arr[$i] == $num) {
                return $i;
            }
        }
        return -1;
    }

    /**
     * [静态查找表] 折半查找/二分查找
     * -------------------------------------------------------------
     * 思路分析：数组中间的值floor((low+top)/2)
     * -------------------------------------------------------------
     * 先取数组中间的值floor((low+top)/2)然后通过与所需查找的数字进行比较，
     * 若比中间值大则将首值替换为中间位置下一个位置，继续第一步的操作；
     * 若比中间值小，则将尾值替换为中间位置上一个位置，继续第一步操作
     * 重复第二步操作直至找出目标数字
     * @param array $arr 待查找区间
     * @param int $key 查找数
     * @return int        返回找到的键
     */
    function binarySearch(array $arr, int $key): int
    {
        // 初始变量值
        $len  = count($arr);
        $low  = 0;
        $high = $len - 1;
        // 最低点比最高点大就退出
        while ($low <= $high) {
            // 以中间点作为参照点比较
            $mid = intval(($low + $high) / 2);
            if ($key == $arr[$mid]) {
                // 查找数与参照点相等，则找到返回
                return $mid;
            } else if ($key < $arr[$mid]) {
                // 查找数比参照点小，舍去右边
                $high = $mid - 1;
            } else {
                // 查找数比参照点大，舍去左边
                $low = $mid + 1;
            }
        }
        // 未找到，返回-1
        return -1;
    }

    /**
     * [静态查找表] 二分查找算法(递归的算法实现)
     * @param array $arr 整形数组 $arr[$lower,...,$high]
     * @param int $key 查找数
     * @param int $lower 区间最低点
     * @param int $high 区间最高点
     * @return int
     */
    function binarySearchRecursion(array $arr, int $key, int $lower, int $high): int
    {
        if ($lower <= $high) {
            // 以区间的中间点作为参照点比较
            $mid = intval(($lower + $high) / 2);
            if ($key == $arr[$mid]) {
                return $mid;
            } elseif ($key < $arr[$mid]) {
                // 查找数比参照点小，舍去右边继续查找
                return $this->binarySearchRecursion($arr, $key, $lower, $mid - 1);
            } else {
                // 查找数比参照点大，舍去左边继续查找
                return $this->binarySearchRecursion($arr, $key, $mid + 1, $high);
            }
        }
        // 最低点比最高点大就退出
        return -1;
    }

    /**
     * [静态查找表] 分块查找/索引顺序查找
     * 顺序查找的改进，效率介于顺序查找与折半查找之间
     * @param array $container
     * @param       $num
     * @return bool|float|int
     */
    public function blockSearch(array $container, $num)
    {
        $count = count($container);
        $lower = 0;
        $high  = $count - 1;

        while ($lower <= $high) {
            if ($container[$lower] == $num) {
                return $lower;
            }
            if ($container[$high] == $num) {
                return $high;
            }

            // 1）在索引表中确认待查询记录所在的块
            $left  = intval($lower + $num - $container[$lower]);
            $right = ($container[$high] - $container[$lower]) * ($high - $lower);

            $middle = $left / $right;

            // 2）在块内顺序查找
            if ($num < $container[$middle]) {
                $high = $middle - 1;
            } else if ($num > $container[$middle]) {
                $lower = $middle + 1;
            } else {
                return $middle;
            }
        }
        return false;
    }
}